package com.Sep_Twenty_Nine;

import java.util.ArrayList;
import java.util.List;

/**
 * 797. 所有可能的路径
 * 给你一个有 n 个节点的 有向无环图（DAG），请你找出所有从节点 0 到节点 n-1 的路径并输出（不要求按特定顺序）
 *
 *  graph[i] 是一个从节点 i 可以访问的所有节点的列表（即从节点 i 到节点 graph[i][j]存在一条有向边）。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/all-paths-from-source-to-target
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * 2022/09/29 13:40
 */

public class Solution797 {

    List<List<Integer>> list=new ArrayList<>();
    List<Integer> path=new ArrayList<>();
    public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
        path.add(0);
        backtracking(graph,0);
        return list;
    }

    public void backtracking(int[][] graph,int x){
        if (x==graph.length-1)
        {
            list.add(new ArrayList<>(path));
            return;
        }
        for (int i=0;i<graph[x].length;i++)
        {
            path.add(graph[x][i]);
            backtracking(graph,graph[x][i]);
            path.remove(path.size()-1);
        }
    }

    public static void main(String[] args) {
        Solution797 solution797=new Solution797();
        int[][] graph={
                {4,3,1},
                {3,2,4},
                {3},
                {4},
                {}
        };
        System.out.println(solution797.allPathsSourceTarget(graph));
    }
}
